package com.wtgroup.demo.leetcode.q1269_停在原地的方案数;

import org.junit.Test;

/**
 * @author 60906
 * @date 2021/5/14 19:33
 */
public class Q1269 {

    @Test
    public void foo1() {
        // int[] input = {3, 2};
        int[] input = {434, 291270};
        // int res = new Solution_Rec().numWays(input[0], input[1]);
        // System.out.println(res);
        // int res1 = new Solution_Dp().numWays(input[0], input[1]);
        // System.out.println(res1);
        int res2 = new Solution_Dp2().numWays(input[0], input[1]);
        System.out.println(res2);
    }


    /**
     * 可以考虑一般情况, 给定起点 a , 重点 b, 步数 k
     */
    class Solution_Rec {
        final int MASK = (int) (Math.pow(10, 9) + 7);

        public int numWays(int steps, int arrLen) {
            if (arrLen == 0) return 0;
            if (arrLen == 1) return 1;
            int r = func(0, 0, steps, arrLen);
            return r % MASK;
        }

        private int func(int start, int dest, int steps, int arrLen) {
            // 步数消耗完了后, 如果当前位置恰好在目标处, 说明之前的步数加起来构成有效方案
            if (steps == 0) {
                return start == dest ? 1 : 0;
            }

            int r = func(start, dest, steps - 1, arrLen) % MASK;
            // 如果当前在 0 , 下一步只能向右; n-1 处, 下一步只能向左
            if (start == 0) {
                return r + func(start + 1, dest, steps - 1, arrLen) % MASK;
            }
            if (start == arrLen - 1) {
                return r + func(start - 1, dest, steps - 1, arrLen) % MASK;
            }
            return r + func(start - 1, dest, steps - 1, arrLen) % MASK + func(start + 1, dest, steps - 1, arrLen) % MASK;
        }
    }

    /**
     * 递归->动态规划
     *
     * 超出内存限制
     */
    class Solution_Dp {
        final int MASK = (int) (Math.pow(10, 9) + 7);

        public int numWays(int steps, int arrLen) {
            if (arrLen == 0) return 0;
            if (arrLen == 1) return 1;

            // 动归参数: start, steps ，当前位置，剩余步数
            int[][] dp = new int[arrLen][steps + 1]; // ! +1
            // 0列
            dp[0][0] = 1; // start==dest 1，剩下的都是0

            int maxRowCnt = Math.min(arrLen - 1, steps); // 当前位置距离0 < 剩余步数, 方案数必是0, 剪枝效果, 矩阵半角不用管

            // 1列开始, 每列依赖前一列三行的
            for (int rest = 1; rest <= steps; rest++) {
                // 0行和arrLen-1行
                dp[0][rest] = (int) ((long)dp[0][rest - 1] + dp[1][rest - 1]) % MASK;
                dp[arrLen - 1][rest] = (int) (((long)dp[arrLen - 1][rest - 1] + dp[arrLen - 2][rest - 1]) % MASK);

                for (int pos = 1; pos < maxRowCnt; pos++) {
                    dp[pos][rest] = (int) (((long)dp[pos][rest - 1] + dp[pos - 1][rest - 1] + dp[pos + 1][rest - 1]) % MASK);
                }
            }

            return dp[0][steps] % MASK;
        }

    }

    /**
     * 数组压缩
     *
     * 超出时间限制 --> 一个半角不管 --> 22%
     *
     * 一个半角不考虑, 用二维数组内存也是可以的, LC 用的就是二维.
     */
    class Solution_Dp2 {
        final int MASK = (int) (Math.pow(10, 9) + 7);

        public int numWays(int steps, int arrLen) {
            if (arrLen == 0) return 0;
            if (arrLen == 1) return 1;

            int posCnt = Math.min(arrLen, steps+1); // 当前位置距离0 < 剩余步数, 方案数必是0, 剪枝效果, 矩阵半角不用管
            // 动归参数: start, steps ，当前位置，剩余步数
            int[] dp = new int[posCnt]; // 内存消耗瞬间降低 99%
            // 0列
            dp[0] = 1; // start==dest 1，剩下的都是0

            // 1列开始, 每列依赖前一列三行的, 自己依赖上一个自己和下一个, 但上一个已经被覆盖了. 故, 覆盖前备份.
            int prev = 0;
            int tmp = 0;
            for (int rest = 1; rest <= steps; rest++) {
                // 0行和arrLen-1行
                tmp = (int) ((long) dp[0] + dp[1]) % MASK;
                prev = dp[0];
                dp[0] = tmp;
                for (int pos = 1; pos < posCnt-1; pos++) {
                    tmp = (int) (((long)dp[pos] + prev + dp[pos + 1]) % MASK);
                    prev = dp[pos];
                    dp[pos] = tmp;
                }
                dp[posCnt - 1] = (int) (((long)dp[posCnt - 1] + prev) % MASK);
            }

            return dp[0] % MASK;
        }

    }
}
